/*
 * @lc app=leetcode.cn id=990 lang=typescript
 *
 * [990] 等式方程的可满足性
 */

// @lc code=start

//  思路：并查集
//  等式成立即连通，将所有等式连通后
//  比较不等式看是否成立（连通），成立则逻辑冲突
//  参考：https://labuladong.github.io/algo/2/18/37/

function equationsPossible(equations: string[]): boolean {
    const uf = new UF(26)
    const A = 'a'.charCodeAt(0)
    // 先让相等的字母形成连通分量
    for (const eq of equations) {
        if (eq[1] === '=') {
            const codeX = eq.charCodeAt(0)
            const codeY = eq.charCodeAt(3)
            uf.union(codeX - A, codeY - A)
        }
    }
    // 检查不等关系是否打破相等关系的连通性
    for (const eq of equations) {
        if (eq[1] === '!') {
            const codeX = eq.charCodeAt(0)
            const codeY = eq.charCodeAt(3)
            // 如果相等关系成立，就是逻辑冲突
            if (uf.connnect(codeX - A, codeY - A)) {
                return false
            }
        }
    }
    return true
};

class UF {
    count: number
    parent: number[]
    size: number[]
    constructor(n: number) {
        this.count = n
        this.parent = new Array(n).fill(0)
        this.size = new Array(n).fill(1)
        for (let i = 0; i < n; i++) {
            this.parent[i] = i
        }
    }
    // 返回x的根节点
    find(x: number): number {
        while (this.parent[x] !== x) {
            // 路径压缩
            this.parent[x] = this.parent[this.parent[x]]
            x = this.parent[x]
        }
        return x
    }
    // 将p、q联通
    union(p: number, q: number) {
        const rootP = this.find(p)
        const rootQ = this.find(q)
        if (rootP === rootQ) return
        if (this.size[rootP] > this.size[rootQ]) {
            this.parent[rootQ] = rootP
            this.size[rootP] += this.size[rootQ]
        } else {
            this.parent[rootP] = rootQ
            this.size[rootQ] += this.size[rootP]
        }
        this.count--
    }
    // 判断p、q是否联通
    connnect(p: number, q: number): boolean {
        const rootP = this.find(p)
        const rootQ = this.find(q)
        return rootP === rootQ
    }
}

// @lc code=end

console.log(equationsPossible(["a==b", "b!=a"]))
console.log(equationsPossible(["b==a", "a==b"]))
console.log(equationsPossible(["a==b", "b==c", "a==c"]))
console.log(equationsPossible(["a==b", "b!=c", "c==a"]))
console.log(equationsPossible(["c==c", "b==d", "x!=z"]))
